package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         22,
		Discription: "生成指定对数的括号组合",
		Level:       2,
		Labels: map[string]int{
			"回溯":  1,
			"递归":  1,
			"计数栈":  1,
			"字符串": 1,
		},
	})
}

func GenerateParenthesis(n int) []string {
	res := make([]string, 0)
	var dfs func(int, int, string)
	dfs = func(s, matchCount int, str string) {
		if matchCount == n {
			res = append(res, str)
			return
		}

		//优先处理栈为空
		if s == 0 {
			dfs(s+1, matchCount, str+"(")
			return
		}

		//是否还能加对数
		if matchCount+s < n {
			dfs(s+1, matchCount, str+"(")
		}

		//加右括号
		dfs(s-1, matchCount+1, str+")")
	}

	dfs(1, 0, "(")
	return res
}